/**
 * Created by fancy on 2017/5/17.
 */
//参考网址：http://www.cnblogs.com/0201zcr/p/4764427.html
/**
 * 插入排序
 *
 * 从第一个元素开始，该元素可以认为已经被排序
 * 取出下一个元素，在已经排序的元素序列中从后向前扫描
 * 如果该元素（已排序）大于新元素，将该元素移到下一位置
 * 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
 * 将新元素插入到该位置中
 * 重复步骤2
 * @param numbers  待排序数组
 */

public class InsertSort {

    public static void insertSort(int[] numbers)
    {
        int size = numbers.length;
        int temp = 0 ;
        int j =  0;

        for(int i = 0 ; i < size ; i++)
        {
            temp = numbers[i];
            //假如temp比前面的值小，则将前面的值后移
            for(j = i ; j > 0 && temp < numbers[j-1] ; j --)
            {
                numbers[j] = numbers[j-1];
            }
            numbers[j] = temp;
        }
    }

    public static void printArr(int[] numbers)
    {
        for(int i = 0 ; i < numbers.length ; i ++ )
        {
            System.out.print(numbers[i] + ",");
        }
        System.out.println("");
    }

    public static void main(String[] args){
        int a[]={49,38,65,97,76,13,27,49};
        System.out.println("排序前的结果：");
        printArr(a);
        insertSort(a);
        System.out.println("插入排序后的结果：");
        printArr(a);
    }
}

// 时间复杂度：O（n^2）.
